package com.fr.question;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月12日
*时间：上午11:16:04
*/
public class ms {
    /**
     * 二叉树序列号和反序列化
     * 思路 遍历树（空节点要补全）
     * */
    @Test
    public void serialize() {
        TreeNode node = new TreeNode(0);
        TreeNode n11 = new TreeNode(11);
        TreeNode n12 = new TreeNode(12);
        TreeNode n21 = new TreeNode(21);
        TreeNode n22 = new TreeNode(22);
        TreeNode n31 = new TreeNode(31);
        TreeNode n33 = new TreeNode(33);
        TreeNode n34 = new TreeNode(34);
        node.left = n11;
        node.right = n12;
        n11.left = n21;
        n11.right = n22;
        n21.left = n31;
        n22.left = n33;
        n22.right = n34;
        String s = serialize(node);
        System.out.println(s);
        TreeNode t = deserialize(s);
        System.out.println(t);

    }

    private String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) {
            return null;
        }
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        boolean isFirst = true;
        boolean hasChild = true;
        while (hasChild) {
            hasChild = false;
            List<TreeNode> list2 = new ArrayList<>();
            for (TreeNode t : list) {
                String code;
                if (t == null) {
                    code = "#";
                    list2.add(null);
                    list2.add(null);
                } else {
                    code = String.valueOf(t.val);
                    if (t.left != null || t.right != null) {
                        hasChild = true;
                    }
                    list2.add(t.left);
                    list2.add(t.right);
                }
                if (isFirst) {
                    sb.append(code);
                    isFirst = false;
                } else {
                    sb.append(",").append(code);
                }
            }
            list = new ArrayList<>(list2);
        }
        return sb.toString();
    }

    private TreeNode deserialize(String data) {
        if (data == null || data.length() <= 0) {
            return null;
        }
        String[] split = data.split(",");
        List<TreeNode> list = new ArrayList<>();
        TreeNode node = new TreeNode(Integer.parseInt(split[0]));
        list.add(node);
        int i = 1;
        a: while (i < split.length) {
            List<TreeNode> list2 = new ArrayList<>();
            for (TreeNode t : list) {
                if (t == null) {
                    list2.add(null);
                    list2.add(null);
                    i += 2;
                } else {
                    t.left = getTreeNode(split[i++]);
                    list2.add(t.left);
                    if (i < split.length) {
                        t.right = getTreeNode(split[i++]);
                        list2.add(t.right);
                    } else {
                        break a;
                    }

                }
                if (i >= split.length) {
                    break a;
                }

            }
            list = new ArrayList<>(list2);
        }
        return node;
    }

    private TreeNode getTreeNode(String s) {
        if (s == null || s.equals("#")) {
            return null;
        }
        return new TreeNode(Integer.parseInt(s));
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {

        }

        public TreeNode(int val) {
            this.val = val;
        }

        public boolean hasChild() {
            if (left == null && right == null) {
                return false;
            }
            return true;
        }
    }

    /**
     * 房屋打劫，圆环
     * */
    static int total = 0;

    @Test
    public void houseRobber2() {
        int[] num = { 828, 125, 740, 724, 983, 321, 773, 678, 841, 842, 875, 377, 674, 144, 340, 467, 625, 916, 463, 922, 255, 662, 692, 123, 778, 766, 254,
                559, 480, 483, 904, 60, 305, 966, 872, 935, 626, 691, 832, 998, 508, 657, 215, 162, 858, 179, 869, 674, 452, 158, 520, 138, 847, 452, 764, 995,
                600, 568, 92, 496, 533, 404, 186, 345, 304, 420, 181, 73, 547, 281, 374, 376, 454, 438, 553, 929, 140, 298, 451, 674, 91, 531, 685, 862, 446,
                262, 477, 573, 627, 624, 814, 103, 294, 388 };
        int lenth = num.length;
        boolean[] hasRobbed = new boolean[lenth];
        rob(0, lenth, num, hasRobbed, 0);
        System.out.println(total);
    }

    private void rob(int i, int lenth, int[] num, boolean[] hasRobbed, int sum) {
        if (i >= lenth) {
            save(sum);
        } else {
            // 不能抢
            if (hasRobbed[(i - 1 + lenth) % lenth] || hasRobbed[(i + 1) % lenth]) {
                rob(i + 1, lenth, num, hasRobbed, sum);
            } else {
                // 能抢
                // 不抢
                rob(i + 1, lenth, num, hasRobbed, sum);
                // 抢
                sum += num[i];
                hasRobbed[i] = true;
                rob(i + 1, lenth, num, hasRobbed, sum);
                sum -= num[i];
                hasRobbed[i] = false;
            }
        }
    }

    private void save(int sum) {
        if (total <= sum) {
            total = sum;
        }
    }

    @Test
    public void tate() {
        System.out.println(-1 % 5);
    }
}
